#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

//BC40
//int main()
//{
//    char vote = 0;
//    int count1 = 0, count2 = 0;
//    while ((vote = getchar()) != '0')
//    {
//        if (vote == 'A')   count1++;
//        else if (vote == 'B')   count2++;
//    }
//    if (count1 > count2)  printf("A");
//    else if (count2 > count1)  printf("B");
//    else printf("E");
//    return 0;
//}


//BC41
//int main()
//{
//    int iq;
//    while (scanf("%d", &iq) != EOF)
//    {
//        if (iq >= 140)
//        {
//            printf("Genius\n");
//        }
//    }
//    return 0;
//}


//BC42
//int main() {
//    int mark = 0;
//    while ((scanf("%d", &mark)) != EOF) {
//        if (mark >= 90 && mark <= 100)   printf("Perfect");
//    }
//    return 0;
//}

//BC43
//int main()
//{
//    int mark = 0;
//    while ((scanf("%d", &mark)) != EOF)
//    {
//        if (mark >= 60)  printf("Pass\n");
//        else printf("Fail\n");
//    }
//    return 0;
//}


//BC44
//int main()
//{
//int a = 0;
//while ((scanf("%d", &a) != EOF)) {
//    if (a % 2 == 0) {
//        printf("Even");
//    }
//    else {
//        printf("Odd");
//    }
//    putchar('\n');
//}
//	return 0;
//}

//BC45
//int main()
//{
//    int a, b, c;
//    scanf("%d%d%d", &a, &b, &c);
//    int max = a;
//    if (b > a)  max = b;
//    if (c > max) max = c;
//    printf("%d", max);
//    return 0;
//}

//BC46
//int main() {
//char a = 0;
//while ((a = getchar()) != EOF) {
//    if (a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u' ||
//        a == 'A' || a == 'E' || a == 'I' || a == 'O' || a == 'U')  printf("Vowel\n");
//    else printf("Consonant\n");
//    getchar();
//}
//return 0;
//}

//BC47
//#include<ctype.h>
//int main()
//{
//    char a = 0;
//    while ((scanf("%c", &a)) != EOF)
//    {
//        if (isalpha(a))  printf("%c is an alphabet.\n", a);
//        else printf("%c is not an alphabet.\n", a);
//        getchar();
//    }
//    return 0;
//}


//BC48
//#include<ctype.h>
//int main() {
//    char a = 0;
//    while ((scanf("%c", &a)) != EOF) {
//        if (isupper(a)) {
//            a = tolower(a);
//            printf("%c\n", a);
//        }
//        else if (islower(a)) {
//            a = toupper(a);
//            printf("%c\n", a);
//        }
//    }
//    return 0;
//}


//BC49
//int size(int a, int  b)
//{
//    if (a > b)
//    {
//        printf("%d>%d", a, b);
//    }
//    else if (a == b)
//    {
//        printf("%d=%d", a, b);
//    }
//    else
//    {
//        printf("%d<%d", a, b);
//    }
//    return 0;
//}
//int main()
//{
//    int  a = 0, b = 0;
//    while ((scanf("%d%d", &a, &b)) != EOF)
//    {
//        size(a, b);
//        putchar('\n');
//    }
//    return 0;
//}


//BC50
//int main()
//{
//    float  num = 0;
//    while (((scanf("%f ", &num)) != EOF))
//    {
//        if (num > 0)  printf("1\n");
//        else if (num == 0)   printf("0.5\n");
//        else printf("0");
//    }
//    return 0;
//}


//BC51
//int main()
//{
//    int j = 0;
//    int k = 0;
//    int m = 0;
//    while ((scanf("%d %d %d", &j, &k, &m)) != EOF)
//    {
//        if ((j + k) > m && (j + m) > k && (m + k) > j)
//        {
//            if (j == k && k == m)
//            {
//                printf("Equilateral triangle!");
//            }
//            else if (j == k || j == m || k == m)
//            {
//                printf("Isosceles triangle!");
//            }
//            else
//            {
//                printf("Ordinary triangle!");
//            }
//        }
//        else
//        {
//            printf("Not a triangle!");
//        }
//        printf("\n");
//    }
//    return 0;
//}

//BC52
//float my_BMI(int weight, int lat)
//{
//    return weight / (lat / 100.0 * lat / 100.0);
//}
//int main()
//{
//    int weight = 0, lat = 0;
//    while ((scanf("%d%d", &weight, &lat)) != EOF)
//    {
//        float BMI = my_BMI(weight, lat);
//        if (BMI < 18.5)   printf("Underweight\n");
//        else if (BMI >= 18.5 && BMI <= 23.9)  printf("Normal\n");
//        else if (BMI > 23.9 && BMI <= 27.9)  printf("Overweight\n");
//        else printf("Obese\n");
//    }
//    return 0;
//}



//BC53
//#include<math.h>
//int main() {
//    double a, b, c;
//    while (((scanf("%lf%lf%lf", &a, &b, &c)) != EOF))
//    {
//        if (a == 0)  printf("Not quadratic equation");
//        else
//        {
//            double x1, x2, shi, xu;
//            double tri = b * b - 4 * a * c;
//            if (tri > 0)
//            {
//                x1 = (-b - pow(tri, 0.5)) / (2 * a);
//                x2 = (-b + pow(tri, 0.5)) / (2 * a);
//                printf("x1=%.2lf;x2=%.2lf\n", x1, x2);
//            }
//            else if (tri == 0)
//            {
//                x1 = -b / (2 * a)+0;
//                printf("x1=x2=%.2lf\n", x1);
//            }
//            else if (tri < 0)
//            {
//                shi = -b / (2 * a);
//                xu = sqrt(-tri) / (2 * a);
//                printf("x1=%.2lf%.2lfi;x2=%.2lf%+.2lfi\n", shi, -xu, shi, xu);
//            }
//        }
//    }
//    return 0;
//}

//BC54
//int main() {
//    int year = 0;
//    int month = 0;
//    while ((scanf("%d%d", &year, &month) != EOF)) {
//        if (year % 4 == 0 && year % 100 != 0 || year % 400 == 0) {
//            switch (month) {
//            case 1:
//            case 3:
//            case 5:
//            case 7:
//            case 8:
//            case 10:
//            case 12:
//                printf("31\n");
//                break;
//            case 4:
//            case 6:
//            case 9:
//            case 11:
//                printf("30\n");
//                break;
//            case 2:
//                printf("29\n");
//            }
//        }
//        else {
//            switch (month) {
//            case 1:
//            case 3:
//            case 5:
//            case 7:
//            case 8:
//            case 10:
//            case 12:
//                printf("31\n");
//                break;
//            case 4:
//            case 6:
//            case 9:
//            case 11:
//                printf("30\n");
//                break;
//            case 2:
//                printf("28\n");
//            }
//        }
//    }
//    return 0;
//}


//BC55
//int main()
//{
//    double a, b;
//    char cal;
//    scanf("%lf%c%lf", &a, &cal, &b);
//    {
//        if (cal == '+')  printf("%.4lf+%.4lf=%.4lf", a, b, a + b);
//        else if (cal == '-')  printf("%.4lf-%.4lf=%.4lf", a, b, a - b);
//        else if (cal == '*')  printf("%.4lf*%.4lf=%.4lf", a, b, a * b);
//        else if (cal == '/')
//        {
//            if (b == 0.0)  printf("Wrong!Division by zero!");
//            else printf("%.4lf/%.4lf=%.4lf", a, b, a / b);
//        }
//        else printf("Invalid operation!");
//    }
//    return 0;
//}


//BC56
//int main()
//{
//    int n = 0, i = 0;
//    while ((scanf("%d", &n)) != EOF) {
//        for (i = 0; i < n; i++) {
//            printf("*");
//        }
//        putchar('\n');
//    }
//    return 0;
//}



//BC57
//int main()
//{
//    int col, row, n;
//    while ((scanf("%d", &n)) != EOF)
//    {
//        for (row = 0; row < n; row++)
//        {
//            for (col = 0; col < n; col++)
//            {
//                printf("* ");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}


//BC58
//int main()
//{
//    int n, row, col;
//    while ((scanf("%d", &n)) != EOF)
//    {
//        for (row = 1; row <= n; row++)
//        {
//            for (col = 1; col <= row; col++)
//            {
//                printf("* ");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}


//BC59
//int main()
//{
//    int n, row, col;
//    while ((scanf("%d", &n)) != EOF)
//    {
//        for (row = n; row >= 1; row--)
//        {
//            for (col = 1; col <= row; col++)
//            {
//                printf("* ");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}


//BC60
//int main()
//{
//    int n, row, col;
//    while ((scanf("%d", &n)) != EOF)
//    {
//        for (row = 1; row <= n; row++)
//        {
//            for (col = 1; col <= n - row; col++)
//            {
//                printf("  ");
//            }
//            for (col = 1; col <= row; col++)
//            {
//                printf("* ");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}


//BC61
//int main()
//{
//    int n, row, col;
//    while ((scanf("%d", &n)) != EOF)
//    {
//        for (row = 1; row <= n; row++)
//        {
//            for (col = 1; col <= n - row; col++)
//            {
//                printf(" ");
//            }
//            for (col = 1; col <= row; col++)
//            {
//                printf("* ");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}


//BC62
//int main()
//{
//    int n, row, col;
//    while ((scanf("%d", &n)) != EOF)
//    {
//        for (row = n; row >= 1; row--)
//        {
//            for (col = 1; col <= n - row; col++)
//            {
//                printf(" ");
//            }
//            for (col = 1; col <= row; col++)
//            {
//                printf("* ");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}


//BC63
//int main() 
//{
//    int n, row, col;
//    while ((scanf("%d", &n)) != EOF)
//    {
//        for (row = 1; row <= n + 1; row++)
//        {
//            for (col = 1; col <= n + 1 - row; col++)
//            {
//                printf(" ");
//            }
//            for (col = 1; col <= row; col++)
//            {
//                printf("* ");
//            }
//            printf("\n");
//        }       
//        for (row = n; row >= 1; row--)
//        {
//            for (col = 1; col <= n + 1 - row; col++)
//            {
//                printf(" ");
//            }
//            for (col = 1; col <= row; col++)
//            {
//                printf("* ");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}


//BC64
//int main()
//{
//    int n, row, col;
//    while ((scanf("%d", &n)) != EOF)
//    {
//        for (row = n + 1; row >= 1; row--)
//        {
//            for (col = 1; col <= row; col++)
//            {
//
//                printf("* ");
//            }
//            printf("\n");
//        }
//        for (row = 2; row <= n + 1; row++)
//        {
//            for (col = 1; col <= row; col++)
//            {
//                printf("* ");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}


//BC65
//int main()
//{
//    int n, row, col;
//    while ((scanf("%d", &n)) != EOF)
//    {
//        for (row = 1; row <= n + 1; row++)
//        {
//            for (col = 1; col <= n + 1 - row; col++)
//            {
//                printf("  ");
//            }
//            for (col = 1; col <= row; col++)
//            {
//                printf("*");
//            }
//            printf("\n");
//        }
//        for (row = 1; row <= n; row++)
//        {
//            for (col = 1; col <= row; col++)
//            {
//                printf("  ");
//            }
//            for (col = n+1-row; col >= 1; col--)
//            {
//                printf("*");
//            }
//            printf("\n");
//        }
//    }
//    return 0;
//}

//BC66
